A key challenge for applying memory-based search heuristics, such as pattern databases (Culberson J., and Schaeffer, J., Pattern databases, Computational Intelligence 14(3):318-334 (1998)) and merge & shrink abstractions (Drager, K., Finkbeiner, B., and Podelski, A., Directed model checking with distance-preserving abstractions; In Model checking software: 13th International SPIN Workshop, Vienna, Austria, March 30-Apr. 1, 2006, proceedings, 19, Springer-Verlag New York Inc. (2006); Helmert, M., Haslum, P., and Hoffmann, J., Flexible abstraction heuristics for optimal sequential planning, In Proc. ICAPS, volume 2007, 176-183 (2007)), to domain-independent planning is succinct representation. The performance of these heuristics usually improves with the size of their underlying data, as well as the efficiency with which they can be accessed, with subsequent consequences to their memory requirements. The problem is exacerbated when employing best-first search algorithms with duplicate detection such as A*, since these algorithms are usually limited by the amount of available memory, a deciding factor for problem solvability.
Linear-space search algorithms such as IDA* (Korf, R., Depth-first iterative-deepening: An optimal admissible tree search, Artificial intelligence (1985)) use much less memory than A* but by foregoing duplicate detection, they pay the price of extra node expansions to find optimal solutions. This time-space tradeoff pays off in domains with few duplicates such as the sliding-tile puzzles where IDA* easily outperforms A*, but many domains (e.g. multiple sequence alignment) are not conducive to this approach. Hence current state-of-the-art heuristic search planners such as Fast Downward (Helmert, M., The fast downward planning system, Journal of Artificial Intelligence Research 26 (2006):191-246 (2006)), HSP_F and Gamer include duplicate detection.
Perfect hashing is a popular technique used to associate subproblems to precomputed solutions. Here, an (injective) enumerating function assigns each subproblem a unique id that is typically used to address a record in a random access structure. However, in domain-independent planning, it is often infeasible to find a function that is also nearly surjective, particularly when dealing with complex subproblems. This quickly leads to excessive amounts of unused slots in the data array, relegating the approach to simple subproblems.
Another approach to representing pattern databases is to use BDDs (Edelkamp, S., Symbolic pattern databases in heuristic search planning, In Proceedings of the 6th International Conference on Al Planning and Scheduling (AIPS-02), 274-283 (2002)). An (ordered and reduced) BDD is a canonical graph-based representation of a binary function that, through merging isomorphic sub-graphs, is often very space efficient. State-sets can be mapped to binary functions straightforwardly and BDDs have been successfully used in planning and model checking (Jensen, R., Bryant, R., and Veloso, M., SetA*: An efficient bdd-based heuristic search algorithm, In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-02), 668-673 (2002)). One problem for domain-independent planning is that the space efficiency of these approaches can vary widely depending on the structure of the underlying domain. Another problem is that BDDs are not well suited for associating data with individual states in a space efficient way. This is usually less of a problem for pattern databases, as often, a significant number of patterns is associated with the same value. Nevertheless, this makes BDDs a challenge to use in more general memoization contexts.